543 Diameter of Binary Tree

thoughts

• 樹的直徑：任意兩個節點之間的最長路徑（經過 root 或不經 root）。
• DFS 計算每個節點的左右子樹高度，更新最大直徑。

kotlin

class Solution {
    private var diameter = 0

    fun diameterOfBinaryTree(root: TreeNode?): Int {
        dfs(root)
        return diameter
    }

    private fun dfs(node: TreeNode?): Int {
        if (node == null) return 0
        val left = dfs(node.left)
        val right = dfs(node.right)
        diameter = maxOf(diameter, left + right)
        return maxOf(left, right) + 1
    }
}

follow up

• 如果要回傳實際的路徑 (而不是長度)，怎麼修改？
• 能否用 BFS + 兩次最遠點搜索 來計算直徑？(樹的直徑經典解法)
• 若樹是動態新增節點，如何維護直徑？